DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2022.74

Correlation Detection in Trees for Planted Graph Alignment

Authors: Luca Ganassali, Laurent Massoulié, and Marc Lelarge

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

Motivated by alignment of correlated sparse random graphs, we study a hypothesis problem of deciding whether two random trees are correlated or not. Based on this correlation detection problem, we propose MPAlign, a message-passing algorithm for graph alignment, which we prove to succeed in polynomial time at partial alignment whenever tree detection is feasible. As a result our analysis of tree detection reveals new ranges of parameters for which partial alignment of sparse random graphs is feasible in polynomial time. We conjecture that the connection between partial graph alignment and tree detection runs deeper, and that the parameter range where tree detection is impossible, which we partially characterize, corresponds to a region where partial graph alignment is hard (not polytime feasible).

Cite as

Luca Ganassali, Laurent Massoulié, and Marc Lelarge. Correlation Detection in Trees for Planted Graph Alignment. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 74:1-74:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ganassali_et_al:LIPIcs.ITCS.2022.74,
  author =	{Ganassali, Luca and Massouli\'{e}, Laurent and Lelarge, Marc},
  title =	{{Correlation Detection in Trees for Planted Graph Alignment}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{74:1--74:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.74},
  URN =		{urn:nbn:de:0030-drops-156709},
  doi =		{10.4230/LIPIcs.ITCS.2022.74},
  annote =	{Keywords: inference on graphs, hypothesis testing, Erd\H{o}s-R\'{e}nyi random graphs}
}

Search Results

Documents authored by Ganassali, Luca

Correlation Detection in Trees for Planted Graph Alignment

Abstract

Cite as

Thanks for your feedback!

Could not send message